package review;

import lev01_beginnerClass.util.HelpUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Review04 {
    public static void main(String[] args) {
        int arr[] = new int[]{2,3,5};

        List<Integer> result = findSpecialSquareNumbers();
        for (int num : result) {
            System.out.println(num);
        }

    }

    public static int findleftmostnoless(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int left = 0;
        int right = arr.length - 1;
        int ans = -1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] >= target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    public static int fortes(int[] arr, int target) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= target) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 给定候选值，通过候选值组合总和为target的组合总数（只返回总数，不返回组合示例）
     *
     * @param arr    候选数组
     * @param target 目标值
     * @return
     */
    public   int getTargetSumGroups(int[] arr, int target) {
        //使用动态规划算法
        int[] dp = new int[target+1];
        //初始化，目标值为0只有一种组合方式，什么都不选
        dp[0] = 1;
        //动态规划
        for(int num : arr){
            for(int i = num;i<=target;i++ ){
                //动态更新dp[i]
                dp[i] += dp[i-num];
            }
        }
        return dp[target];
    }


    /**
     * 获取特定条件的完全平方数
     * @return
     */
    private static List<Integer> findSpecialSquareNumbers() {
        List<Integer> specialNumbers = new ArrayList<>();
        int upperLimit = (int) Math.sqrt(9999999);  // 上限是3162 (3162^2 = 9998916 < 9999999)

        for (int i = 1; i <= upperLimit; i++) {
            int square = i * i;
            if (hasExactlyTwoSameDigits(square)) {
                specialNumbers.add(square);
            }
        }

        return specialNumbers;
    }

    private static boolean hasExactlyTwoSameDigits(int number) {
        int[] digitCount = new int[10];  // 记录每个数字出现的次数

        while (number > 0) {
            int digit = number % 10;
            digitCount[digit]++;
            number /= 10;
        }

        boolean foundPair = false;

        for (int count : digitCount) {
            if (count == 2) {
                if (foundPair) {  // 如果已经找到一个2，则不满足条件
                    return false;
                }
                foundPair = true;
            } else if (count > 2) {  // 如果某个数字出现次数超过2，则不满足条件
                return false;
            }
        }

        return foundPair;  // 确保有且仅有一个数字出现2次
    }
}
